%\section{Proof for WeightedInternalCover in NP-complete}
WEIGHTEDINTERVALCOVER is NP-complete. We use  [Partition] as a reference problem. Let $X_1=s_1,\cdots, s_n$ be the input for [Partition]. We construct the corresponding input for [WEIGHTEDINTERVALCOVER] in two phases.
\begin{enumerate}
\item[Phase 1.] All zero elements from $X_1$ are omited yielding $X_1'=s_1',\cdots,s_m'$, $m \leq n$. We claim that an algorithm that solves [PARTITION] would answer YES when $X_1$ is provided as input if and only if it answer YES when $X_1'$ is given as input. Why? If there is a partition of $X_1$ into two disjoint groups with equal sums, then, by omiting the zeros in each of the groups we would get an partition of $X_1'$. If, on the other hand, there is a partition of $X_1'$, by assigning all omited zeros to one of the groups we obtain a partition of $X_1$. Therefore, considering $X_1'$ instead of $X_1$ is safe in terms of preserving the correct answer.
\item[Phase 2.] We construct the input,$X_2$, for [WEIGHTEDINTERVALCOVER]  in the following way
\begin{displaymath}
\begin{array}{l}
y_1=s_1'\\
y_2=s_1'+s_2'\\
\vdots\\
y_m=s_1'+\cdots+s_m'\\
y_{m+1}=\frac{1}{2}\sum_{i=1}^m s_i'
\end{array}
\end{displaymath}
and
\begin{displaymath}
K=m
\end{displaymath}
\end{enumerate}

Without loss of generality we can assume that $y_{m+1}$ is a natural number; the question of existence of partition of $s_1',\cdots,s_m'$ is immaterial when $\sum_{i=1}^m s_i'$ is not an even number.

Clearly, $X_1$ is transformed into $X_2$ in polynomial time; both phase 1 and phase two have linear running time $O(n)$.

In what follows, we use the term ``covers'' to emphasize that a set of weighted intervals satisfies the conditions given by the formulation of [WEIGHTEDINTERVALCOVER] or in other words it is a \emph{weighed interval cover} of the given sequence of numbers. 

\emph{We claim that there is a partition of $s_1',\cdots,s_m'$ if and only if there is a set of weighted intevals with cardinality at most $K$, that ``covers'' the sequnce $y_1,\cdots,y_{m+1}$.}

First, we assume that $s_1',\cdots,s_m'$ can be partitioned in two disjoint groups with equal sums, that is, there is  a set $A \subseteq \{1,\cdots,m\}$ such that
\begin{displaymath}
	\sum_{i\in A}s_i' = \sum_{i\in \{1,\cdots,m\}-A}s_i' = \frac{1}{2}\sum_{i=1}^m s_i'
\end{displaymath}
 We observe the following set of weighted intervals
\begin{eqnarray}
I &=& \{<[i,m+2],s_i'> | i \in A\} \cup  \{<[i,m+1],s_i'> | i \in \{1,\cdots,m\}-A\} \label{sol1}
\end{eqnarray}
For each $i \in A$ ($i \in \{1,\cdots,m\}-A$) an interval with weight $s_i'$ that spans all $y$-s from $y_i$ through $y_{m+1}$ (from $y_i$ through $y_m$) is constructed. Clearly, (\ref{sol1}) satisfies the constraints set by $X_2$.

To prove the converse claim we establish some results first. For a given sequence $y_1,\cdots,y_n$  we use $C(y_1,\cdots,y_n)$ to denote the cardinality of the minimal set of weighted intervals that ``covers'' $y_1,\cdots,y_n$.

\begin{lemma}\label{monotonicity} Let $y_1,\cdots,y_n,y_{n+1}$ be a sequence of natural numbers. The following holds
\begin{displaymath}
	C(y_1,\cdots,y_n) \leq C(y_1,\cdots,y_n,y_{n+1})
\end{displaymath}
\end{lemma}
$\mathbf{Proof:}$ Let $I$ be the minimal set of weighted interval that ``covers'' $y_1,\cdots,y_n,y_{n+1}$. We construct a set of intervals $I'$ out of $I$ by performing the following two transformations:
\begin{enumerate}
\item[i)] All intervals in $I$ that span only $y_{n+1}$ (i.e. intervals within $(n+\frac{1}{2},n+2]$ range) are removed.
\item[ii)] Each interval in $I$, $[a_i,b_i]$, that spans $y_{n+1}$ and (at least) $y_n$ is replaced by $[a_i,n+1]$; it's shrinked from the right so that it will no longer span $y_{n+1}$.
\end{enumerate}
Clearly, $I'$ ``covers'' $y_1,\cdots,y_n$ and $|I'| \leq C(y_1,\cdots,y_n,y_{n+1})$. However, as $C(y_1,\cdots,y_n)$ is the cardinality of the minimal set that ``covers'' $y_1,\cdots,y_n$ we get
\begin{displaymath}
C(y_1,\cdots, y_n)\leq|I'|
\end{displaymath}
Therefore,
\begin{displaymath}
C(y_1,\cdots,y_n)\leq C(y_1,\cdots,y_n,y_{n+1})
\end{displaymath}

\begin{lemma}\label{card} Let $y_1,\cdots,y_n$ be a strickly monotonicaly increasing sequence of natural numbers $(0<y_1<\cdots<y_n)$. The following holds
\begin{displaymath}
	C(y_1,\cdots,y_n) = n
\end{displaymath}
\end{lemma}
$\mathbf{Proof:}$ We establish this claim using mathematical induction on the length of the sequence.

For $n=1$ and $n=2$ the result trivially holds. Let us now assume that the result is valid for any strickly monotonicaly increasing sequence $y_1,\cdots,y_n$ of $n$ natural numbers. We shall prove that $C(y_1,\cdots,y_n,y_{n+1})=n+1$.
Using the induction hypothesis and lemma \ref{monotonicity} we obtain
\begin{displaymath}
	n=C(y_1,\cdots, y_n) \leq C(y_1,\cdots, y_n, y_{n+1})
\end{displaymath}
Lets now assume that $C(y_1,\cdots, y_n, y_{n+1})=n$. The minimal set of weighted intervals is denoted by $I$. Two cases may emerge
\begin{enumerate}
\item [i)] There is no interval that spans only $y_{n+1}$. In other words, all intervals that span $y_{n+1}$, span $y_n$ as well. Consequently, $y_n\geq y_{n+1}$.  But this contradicts our assumption of $y_1,\cdots,y_n,y_{n+1}$ being strictly monotonically increasing.
\item[ii)] There is (at least one) interval that spans only $y_{n+1}$. We construct a set of intervals $I'$ out of $I$ by performing the following two transformations:
	\begin{enumerate}
	\item All intervals that span only $y_{n+1}$ are removed.
	\item  Each interval in $I$, $[a_i,b_i]$, that spans $y_{n+1}$ and (at least) $y_n$ is replaced by $[a_i,n+1]$; it's shrinked from the right so that it will no longer span $y_{n+1}$.
	\end{enumerate}
Clearly, $I'$ ``covers'' $y_1,\cdots,y_n$ and $|I'|\leq n-1$. But this contradicts the inductive hypothesis.
\end{enumerate}
Hence, $C(y_1,\cdots, y_n, y_{n+1})\geq n+1$. There is, however, a set of intervals, namely, $\{<[i,i+1],y_i> | i \in \{1,\cdots,n+1\}\}$, with cardinality $n+1$ that ``covers'' $y_1,\cdots,y_{n+1}$. Thus, we conclude that $C(y_1,\cdots, y_n, y_{n+1})= n+1$.
% \end{enumerate}

Now, we return to the main result. We assume that there is a set of intervals with cardinality at most $m$ that  ``covers'' the sequence $y_1,\cdots,y_m, y_{m+1}$ defined above. We aim to prove two claims (once these claims are proven the validity of the main result follows immediately)
\begin{enumerate}
\item[1.] All intervals that span $y_{m+1}$ also span $y_m$.
\item[2.] All intervals $<[a_j,b_j],c_j>$, $j\in I_k$, that span $y_k$, $k=1,\cdots,m$ have weights defined as follows
\begin{displaymath}
c_j=\sum_{s \in A_j}s
\end{displaymath}
 where $A_j\subseteq \{s_1',\cdots,s_k'\}$, $j \in I_k$ and all $A_j$ are pairwise disjoint. For example, if $<[a_1,b_1],c_1>$ and $<[a_2,b_2],c_2>$ are the only weighted intervals  that, say, span $y_h$ (i.e. $h+\frac{1}{2} \in [a_1,b_1]$ and $h+\frac{1}{2} \in [a_2,b_2]$), then there is a set $A \subseteq \{s_1',\cdots,s_h'\}$ such that $c_1=\sum_{s \in A} s$ and $c_2=\sum_{s \in \{s_1',\cdots,s_h'\}-A} s$.
\end{enumerate}

We start with the first claim. The prove is by contradiction. We assume that there is a weighted interval than spans only $y_{m+1}$.  In the same  way as in the proof of lemma \ref{monotonicity} and lema \ref{card} (by removing and shrinking intervals) we construct a weighted inteval cover, $I'$, of $y_1,\cdots,y_m$ with cardinality at most $m-1$. However, as all $s_i'$ are greater than 0 we conclude that $y_1,\cdots,y_m$ is a strictly monotonicaly increasing sequence. Using lemma \ref{card} we deduce that the cardinality of the minimal weighted interval cover of $y_1,\cdots,y_m$ is exactly $m$. This contradicts the previously established result regarding the cardinality of $I'$! Hence, it follows that all intervals that span $y_{m+1}$ also span $y_m$.

Now, we turn our attention to the second claim. We conduct the prove using mathematical induction on the sequence index. We use $I_k$ to denote the index set of all weighted intervals that span $y_k$, $k=1,\cdots,m+1$ and  $I_{k,k+1}$ to denote the index set of all weighted intervals that span both $y_k$ and $y_{k+1}$, $k=1,\cdots,m$.

First, the base case, $k=1$, is considered. Let us assume that $<[a_1,b_1],c_1>$ is member of the weighted interval cover and it spans $y_1$ i.e. $1+\frac{1}{2} \in [a_1,b_1]$. We will show that assuming $c_1<s_1'$ leads to contradiction. 

If $c_1<s_1'$ is, indeed, valid, we proceed as follows. Firstly, we remove $<[a_1,b_1],c_1>$ from the weighted interval cover yielding a new set of $m-1$ intervals. Secondly, we remove the effect of having $<[a_1,b_1],c_1>$, altogether; if $<[a_1,b_1],c_1>$ spans the first $l$ $y$-s, $y_1,\cdots, y_l$, a new sequence is constructed as follows 
\begin{displaymath}
y_1-c_1, \cdots,y_l-c_1,y_{l+1},\cdots,y_m,y_{m+1}
\end{displaymath}
Clearly, the new interval set (with cardinality $m-1$) is a weighted interval cover of $y_1-c_1, \cdots,y_l-c_1,y_{l+1},\cdots,y_m,y_{m+1}$. But, as $y_1-c_1, \cdots,y_l-c_1,y_{l+1},\cdots,y_m$  is a strictly monotonically increasing sequence of non-zero naturals, according to lemma \ref{card} it has a minimal weighted interval cover with cardinality $m$. As a result, according to lemma \ref{monotonicity} any weighted interval cover of $y_1-c_1, \cdots,y_l-c_1,y_{l+1},\cdots,y_m,y_{m+1}$  should contain at least $m$ intervals. Contradiction! Hence, $c_1\geq s_1'$. But, as $c_1\leq s_1'$ it must be the case that $c_1= s_1'$. Consequently, $y_1$ is spanned only by $<[a_1,b_1],c_1>$ where $c_1=s_1'$. The claim holds.

Next, we assume that the claim is true for $k$ and prove it for $k+1\leq m$. We begin by considering the set of intervals $<[a_j,b_j],c_j>$, $j \in I_{k,k+1}$ that spans both $y_k$ and $y_{k+1}$. According to inductive hypothesis and the fact  that $I_{k,k+1}\subseteq I_k$ their weights are defined as follows 
\begin{eqnarray}\label{weights}
c_j=\sum_{s \in A_j}s
\end{eqnarray}
 where $A_j\subseteq \{s_1',\cdots,s_k'\}$, $j \in I_{k,k+1}$ and all $A_j$ are pairwise disjoint. 

We proceed by removing all intervals that span at least one of the first $k$ numbers. The removal is performed in such a way so that the rest of the intervals still form weighted interval cover. We start with $y_1,\cdots,y_m, y_{m+1}$. Let $<[a,b],c>$ be the first interval to be removed. Furthermore, let us assume that $<[a,b],c>$ spans all $y$-s from $y_l$ through $y_r$ (We bear in mind that $l\leq k$ - $<[a,b],c>$ spans at least one of the first $k$ sequence members). Firstly, we erase $<[a,b],c>$ from the weighted interval cover yielding a new set $I'$ of $m-1$ intervals. Secondly, we erase the effect of having $<[a,b],c>$, altogether. The resulting sequence is given by 
\begin{displaymath}
y_1,\cdots,y_l-c,y_{l+1}-c,\cdots,y_r-c,y_{r+1},\cdots,y_{m+1}
\end{displaymath}
Obviously, $I'$ is weighted interval cover of $y_1,\cdots,y_l-c,y_{l+1}-c,\cdots,y_r-c,y_{r+1},\cdots,y_{m+1}$. As next step, we select another interval (if any) that is to be deleted and perform the same procedure, but this time on $y_1,\cdots,y_l-c,y_{l+1}-c,\cdots,y_r-c,y_{r+1},\cdots,y_{m+1}$. And so on until there are intervals left - each time using the sequence obtained by the removal of the previous interval. Once the process is finished the following sequence is obtained as a result 
\begin{eqnarray}\label{seq}
0,\cdots,0,y_{k+1}',\cdots,y_{m+1}' 
\end{eqnarray}
where $y_{k+1}'=y_{k+1}-\sum_{j \in I_{k,k+1}}c_j$ ($c_j$ given by (\ref{weights})); there are  exactly $k$ leading zeros. Couple of things should be noted. First, it is straightforward to prove, using lemma \ref{monotonicity} and lemma \ref{card}, that the number of erased intervals is $k$. Second, it follows from the way the construction is performed that the remaining $m-k$ intervals form a weighted interval cover of (\ref{seq}) and that $y_{k+1}',\cdots,y_m'$ is a strictly monotonicaly increasing sequence. And third, $y_{k+1}'>0$, otherwise $y_{k+1}\leq y_k$ would hold. Clearly, this puts us in the same situation as we were in the base case. By the same line of reasoning we can prove that $y_{k+1}'$ is covered by a single interval $<[a,b],c>$ where $c=y_{k+1}-\sum_{j \in I_{k,k+1}}c_j$. This concludes the prove of the second claim.

It is time to put everything together. So far, we have proven (first claim) that all intervals $<[a_j,b_j],c_j>$, $j \in I_{m+1}$ that span $y_{m+1}$ must also span $y_m$ i.e. $I_{m+1}\subseteq I_m$. And according to the second claim the weights of these intervals must satisfy the following
\begin{eqnarray}\label{eq1}
c_j=\sum_{s \in A_j}s
\end{eqnarray}
 where $A_j\subseteq \{s_1',\cdots,s_m'\}$, $j \in I_{m+1}$ and all $A_j$ are pairwise disjoint. 

Furthermore, 
\begin{eqnarray}\label{eq2}
\frac{1}{2}\sum_{i=1}^m s_i' = y_{m+1} = \sum_{j \in I_{m+1}} c_j
\end{eqnarray}
is also valid.

Finally, by combining (\ref{eq1}) and (\ref{eq2}) we conclude that $s_1',\cdots,s_m'$ can be partitioned into two disjoint groups with equal sums. Thus, we proved that [WEIGHTEDINTERVALCOVER] is NP-complete.